package LeetCode_SingleLinkedlist;

/**
 * Created with IntelliJ IDEA.
 * Description:链表分割问题
 * User: 阿宾
 * Date: 2024-11-06
 * Time: 20:14
 */
public class Demo5 {
    public static class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public static ListNode partition(ListNode pHead, int x) {
        //链表为空情况
        if(pHead ==  null){
            return null;
        }
        ListNode lessNode = new ListNode(-1);//指向小于x的链表头结点
        ListNode greaterNode = new ListNode(-1);//指向大于x的链表头结点

        ListNode lessTail = lessNode;
        ListNode greaterTail = greaterNode;

        while(pHead != null){
            if(pHead.val < x){
                lessTail.next = pHead;//插入结点
                lessTail = pHead;//更新尾结点
            }else{
                greaterTail.next = pHead;
                greaterTail = pHead;
            }
            pHead = pHead.next;
        }
        lessTail.next = greaterNode.next;
        greaterTail.next = null;//防止发生循环
        return lessNode.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(12, new ListNode(23,new ListNode(56,new ListNode(5,new ListNode(3)))));
        ListNode result = partition(l1,20);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}